package stage1.module3.homework2;

import java.util.ArrayList;

public class Homework2 {


    //s1为较长字符串，s2为较短字符串
    public ArrayList<String> search(String s1, String s2){
        int maxLength = 0;  //记录最长字符串的长度
        ArrayList<String> maxString = new ArrayList<>(); //记录最长字符串（可能有多个）

        for (int i = 0; i < s2.length(); i++){
            //若s2的子串长度小于maxLength则停止搜索
            if(s2.length() - i < maxLength){
                break;
            }
            String subStr = s2.substring(i);

            //先遍历s1找到与subStr第一个字符相等的字符，再对剩余字符进行匹配，看有多少相等的字符

            for(int j = 0; j < s1.length(); j++){
                ////若s1的子串长度小于maxLength则停止搜索
                if(s1.length() - j < maxLength){
                    break;
                }
                //找到与subStr第一个字符相等的字符
                if(s1.charAt(j) == subStr.charAt(0)){
                    int length = 1;
                    //进行匹配
                    for(int k = 1; k < Math.min(subStr.length(), s1.length() - j); k++){
                        if(s1.charAt(j + k) == subStr.charAt(k)){
                            length += 1;
                        }else{
                            break;
                        }
                    }

                    //若匹配的字串长度大于等于已有的最大字串，则记录
                    if(length > maxLength){
                        maxString = new ArrayList<>();
                        maxString.add(subStr.substring(0, length));
                        maxLength = length;
                    }else if(length == maxLength){
                        maxString.add(subStr.substring(0, length));
                    }
                }
            }
        }
        return maxString;
    }
}
